package leetcode

import kotlinetc.println

//https://leetcode.com/problems/largest-rectangle-in-histogram/

/**
Example:

Input: [2,1,5,6,2,3]
Output: 10
 */

fun main(args: Array<String>) {

    largestRectangleArea(intArrayOf(2, 1, 5, 6, 2, 3)).println()
}

//TODO
fun largestRectangleArea(heights: IntArray): Int {


    val stack = arrayListOf<Int>()

    stack.add(0)
    var maxArea = 0
    for (i in 0 until heights.size) {

        while (stack.isNotEmpty() && heights[i] < heights[stack.last()]) {

            val top = stack.removeAt(stack.lastIndex)

            maxArea = Math.max(maxArea, heights[top] * (i - top))

        }
        stack.add(i)
    }

    return maxArea
}